import utils.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class ListSolutions {
    /**
     * easy 206. 反转链表
     */
    // 反转链表——迭代
    public ListNode reverseList(ListNode head) {
        // 迭代法
        ListNode pre = null;
        ListNode node = head;
        while (node != null) {
            ListNode tempNext = node.next;
            node.next = pre;
            pre = node;
            node = tempNext;
        }
        return pre;
    }

    // 反转链表——递归
    public ListNode reverseList_(ListNode head) {
        // 递归法
        if (head == null || head.next == null)
            return head;
        ListNode headNext = head.next;
        head.next = null;
        ListNode newHead = reverseList_(headNext);
        headNext.next = head;
        return newHead;
    }

    /**
     * mid 92. 反转链表 II
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null)
            return null;
        ListNode begin = null, end = null;
        ListNode preEnd = null, nextBegin = null;
        ListNode headPre = new ListNode();
        headPre.next = head;
        ListNode node = head, nodePre = headPre;
        int index = 1;
        while (node != null) {
            if (index == left) {
                begin = node;
                preEnd = nodePre;
            }
            if (index == right) {
                end = node;
                nextBegin = node.next;
                break;
            }
            nodePre = node;
            node = node.next;
            index++;
        }
        node = begin;
        nodePre = null;
        while (node != nextBegin) {
            ListNode next = node.next;
            node.next = nodePre;
            nodePre = node;
            node = next;
        }
        preEnd.next = end;
        begin.next = nextBegin;
        return headPre.next;
    }

    // hard 25. K 个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null)
            return null;
        // 1. 实际交换节点，而不是改变值 2. 要求O（1）空间复杂度
        ListNode preEnd = null;
        ListNode nowStart = head;
        int count = 0;
        ListNode node = head;
        while (node != null) {
            count++;
            if (count == k) {
                // 1. 暂存
                ListNode nextStart = node.next;
                ListNode nowEnd = node;
                // 2. 翻转处理 从 nowStart 到 nowEnd
                ListNode n = nowStart, pre = null;
                while (n != nextStart) {
                    ListNode nNext = n.next;
                    n.next = pre;
                    pre = n;
                    n = nNext;
                }
                if (preEnd != null)
                    preEnd.next = nowEnd; // 如果有上一组,赋值为上一组的
                else
                    head = nowEnd; // 如果是第一组,改变head指针
                nowStart.next = nextStart;
                // 3. 迭代赋值
                node = nextStart;
                count = 0;
                preEnd = nowStart;
                nowStart = nextStart;
            } else {
                node = node.next;
            }
        }
        return head;
    }

    /**
     * mid 21. 合并两个有序链表
     */
    // 递归写法
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }

    // 去重写法-递归
    public ListNode mergeTwoListsUnique(ListNode list1, ListNode list2) {
        // 如果有一方是空的,直接把另一个去重即可
        if (list1 == null || list2 == null) {
            ListNode head = (list1 == null) ? list2 : list1;
            ListNode node = head;
            ListNode dummy = new ListNode();
            dummy.next = head;
            ListNode p = dummy;
            while (node != null) {
                while (node.next != null && node.next.val == node.val)
                    node = node.next;
                p.next = node;
                node = node.next;
                p = p.next;
            }
            return dummy.next;
        }
        // 如果某个链表的下一个是一样的,返回和下一个合并的结果
        if (list1.next != null && list1.val == list1.next.val)
            return mergeTwoListsUnique(list1.next, list2);
        if (list2.next != null && list2.val == list2.next.val)
            return mergeTwoListsUnique(list1, list2.next);
        // 如果这两个链表的当前节点值相等,固定取第二个节点的下一个
        if (list1.val == list2.val)
            return mergeTwoListsUnique(list1, list2.next);
        // 常规写法
        if (list1.val < list2.val) {
            list1.next = mergeTwoListsUnique(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoListsUnique(list1, list2.next);
            return list2;
        }
    }

    // 迭代写法
    public ListNode mergeTwoLists_(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        ListNode node1 = list1, node2 = list2;
        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                p.next = node1;
                node1 = node1.next;
            } else {
                p.next = node2;
                node2 = node2.next;
            }
            p = p.next;
        }
        if (node1 != null)
            p.next = node1;
        if (node2 != null)
            p.next = node2;
        return dummy.next;
    }

    // 去重写法-迭代
    public ListNode mergeTwoLists_Unique(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;

        while (list1 != null && list2 != null) {
            // 在每个链表内,发现下一个和这个相等,则一直找到最后一个
            while (list1.next != null && list1.val == list1.next.val)
                list1 = list1.next;
            while (list2.next != null && list2.val == list2.next.val)
                list2 = list2.next;
            // 如果当前两个链表的值相等了,默认让第二个往后一个,不进行选择
            if (list1.val == list2.val) {
                list2 = list2.next;
                continue;
            }
            // 常规写法
            if (list1.val < list2.val) {
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        // 常规写法,找到剩余的那个链表
        ListNode node = list1 != null ? list1 : list2;
        // 如果剩余的那个链表的部分还有重复的,也要去重
        while (node != null) {
            while (node.next != null && node.val == node.next.val) {
                node = node.next;
            }
            p.next = node;
            node = node.next;
            p = p.next;
        }
        return dummy.next;
    }

    /**
     * hard 23. 合并 K 个升序链表
     */
    // 合并多个有序链表
    public ListNode mergeMultiList(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        for (ListNode list : lists) {
            if (list != null)
                priorityQueue.offer(list);
        }
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        while (!priorityQueue.isEmpty()) {
            ListNode node = priorityQueue.poll();
            ListNode next = node.next;
            p.next = node;
            p = p.next;
            p.next = null; // 这句可以不加
            if (next != null)
                priorityQueue.offer(node.next);
        }
        return dummy.next;
    }

    /**
     * easy 141. 环形链表
     */
    // 判断是否有环形链表
    public boolean hasCycle(ListNode head) {
        if (head == null)
            return false;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    /**
     * mid 142. 环形链表 II
     */
    // 找到环形链表的起始位置
    public ListNode detectCycle(ListNode head) {
        if (head == null)
            return null;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode find = head;
                while (find != slow) {
                    find = find.next;
                    slow = slow.next;
                }
                return find;
            }
        }
        return null;
    }

    /**
     * mid 143. 重排链表
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;
        // 1. 先分割为两个链表
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode list1 = head, list2 = slow.next;
        slow.next = null;
        // 2. 反转后面的链表
        ListNode pre = null, node = list2;
        while (node != null) {
            ListNode next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        list2 = pre;
        // 3. 合并链表
        ListNode preHead = new ListNode();
        preHead.next = head;
        ListNode p = preHead;
        while (list1 != null && list2 != null) {
            p.next = list1;
            p = p.next;
            list1 = list1.next;
            p.next = list2;
            p = p.next;
            list2 = list2.next;
        }
        p.next = list1;
    }

    /**
     * mid 82. 删除排序链表中的重复元素 II
     */
    public ListNode deleteDuplicates2(ListNode head) {
        // 哑节点
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode node = head;
        while (node != null) {
            // 判断当前元素在后面有没有重复
            if (node.next == null || node.val != node.next.val) {
                // 如果没重复,加上这个节点
                pre.next = node;
                pre = node;
                node = node.next;
            } else {
                // 如果重复了,跳过
                int val = node.val;
                while (node != null && node.val == val) {
                    node = node.next;
                }
            }
        }
        pre.next = null;
        return dummy.next;
    }

    /**
     * mid 19. 删除链表的倒数第 N 个结点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode temp = dummy;
        for (int i = 0; i < n; i++)
            temp = temp.next;
        ListNode pre = dummy;
        while (temp.next != null) {
            temp = temp.next;
            pre = pre.next;
        }
        ListNode del = pre.next;
        ListNode next = del.next;
        pre.next = next;
        if (del == head)
            return next;
        else
            return head;
    }

    /**
     * 148. 排序链表
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        // 归并排序 找到左链和右链
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode rightList = slow.next, leftList = head;
        slow.next = null;
        // 递归
        ListNode leftSorted = sortList(leftList);
        ListNode rightSorted = sortList(rightList);
        // 归并
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        ListNode left = leftSorted, right = rightSorted;
        while (left != null && right != null) {
            if (left.val < right.val) {
                p.next = left;
                left = left.next;
            } else {
                p.next = right;
                right = right.next;
            }
            p = p.next;
        }
        if (left != null)
            p.next = left;
        else if (right != null)
            p.next = right;
        return dummy.next;
    }

    /**
     * LCR 140. 训练计划 II
     */
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode fast = dummy;
        for (int i = 0; i < cnt; i++) {
            fast = fast.next;
        }
        ListNode slow = dummy;
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 234. 回文链表
     */
    public boolean isPalindrome(ListNode head) {
        // o1空间复杂度 on时间复杂度
        if (head == null || head.next == null)
            return true;
        // 找到中间位置；翻转后半链表；对比
        ListNode slow = head, fast = head.next, pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        // 如果 fast == null 说明有奇数个，如果 fast.next == null 说明有偶数个
        ListNode node = slow.next;
        if (fast == null) {
            pre.next = null;
        } else {
            slow.next = null;
        }
        pre = null;
        while (node != null) {
            ListNode tempNext = node.next;
            node.next = pre;
            pre = node;
            node = tempNext;
        }
        ListNode node1 = head, node2 = pre;
        while (node1 != null && node2 != null) {
            if (node1.val != node2.val)
                return false;
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1 == null && node2 == null;
    }

    /**
     * 83. 删除排序链表中的重复元素
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;
        ListNode node = head, next = head.next;
        while (next != null) {
            while (next != null && next.val == node.val)
                next = next.next;
            node.next = next;
            node = next;
            if (next != null)
                next = next.next;
        }
        return head;
    }

    /**
     * 24. 两两交换链表中的节点
     */
    public ListNode swapPairs(ListNode head) {
        // 空或只有一个
        if (head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode first = head, pre = dummy;
        while (first != null && first.next != null) {
            ListNode last = first.next, next = last.next;
            last.next = first;
            first.next = next;
            pre.next = last;
            // 更新状态
            pre = first;
            first = next;
        }
        return dummy.next;
    }
}
